package Algorithm.backTracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 77. 组合 https://leetcode.cn/problems/combinations
 * 题目简述：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 */
public class Combine {

    public static void main(String[] args) {
        new Combine().combine(4,2);
    }

    /**
     * 思路：回溯算法解决组合问题，将回溯过程抽象为一棵树形结构
     * 回溯递归函数参数：（结果result，已选择路径，下一步的选择列表）
     * 回溯递归函数体：1.判断当前已选择路径是否已满足要求，若满足则返回
     *              2.遍历选择列表：选择后加入路径，递归下一步的选择列表，完毕后回溯撤销上一步路径选择，继续遍历同层中的其它路径
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        //初始路径选择列表为[1, n]
        backTracking(result, path, 1, n, k);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int s, int n, int k) {
        if(path.size() == k) {
            //路径已满足要求，返回
            result.add(new ArrayList<>(path));
            return;
        }
        //遍历选择列表[s, n]。剪枝1：顺序性剪枝，剪去[0,s)；剪枝2：此时[i, n]中至少还要k-path.size()个数，路径长度不够的分支就无需遍历了
        for(int i=s;i <= n - (k - path.size()) + 1;i++) {
            //加入选择路径
            path.add(i);
            //backTracking(已选择路径，下一步的选择列表)
            backTracking(result, path, i+1, n, k);
            //回溯，撤销上一步路径选择，继续遍历同层中的其它路径
            path.removeLast();
        }
    }
}
